"""
https://leetcode.cn/problems/merge-k-sorted-lists/description/

23. 合并 K 个升序链表
已解答
困难
相关标签
相关企业
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]
 

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
"""

# Definition for singly-linked list.
from typing import List, Optional
import bisect


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    """
    一个思路是，直接将所有链表都拆分开，拆分成一个节点集合，在处理为升序的方式
    这样的缺点是浪费了初始链表升序的特点

    另一个思路是，创建一个新的空链表。并获取所有链表数组的首元素，求取其最小值，逐次放到空链表中。
    这样，问题就变成了如何维护一个动态的升序列表（过程中要对该列表进行增加元素和移除元素操作）。
    这个步骤可以使用二叉顺序树实现：这个步骤有点儿繁琐，可以直接用现成的方案（在java中是TreeMap,在python中则是bisect）。
    """

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        rp=ListNode()
        temp=rp

        top_list=[]
        for node in lists:
            if node is not None:
                bisect.insort(top_list,node,key=lambda x: x.val)

        while top_list:
            min_top=top_list.pop(0)
            temp.next=min_top
            if min_top.next is not None:
                bisect.insort(top_list,min_top.next,key=lambda x: x.val)
            temp=min_top

        return rp.next

if __name__=='__main__':
    s=Solution()

    # node1=ListNode(1,ListNode(4,ListNode(5)))
    # node2=ListNode(1,ListNode(3,ListNode(4)))
    # node3=ListNode(2,ListNode(6))
    # lists=[node1,node2,node3]
    lists=[]

    res=s.mergeKLists(lists)
    lis=[]
    while res is not None:
        lis.append(res.val)
        res=res.next

    print(f'list:{lis}')    

        

    pass